package LeetCode._02算法基础.day10递归回溯;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 挚爱之夕
 * @date 2022 - 03 - 21 - 17:43
 * @Description 给你一个 无重复元素 的整数数组candidates 和一个目标整数target，
 * 找出candidates中可以使数字和为目标数target 的 所有不同组合 ，并以列表形式返回。
 * 你可以按 任意顺序 返回这些组合。
 * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
 * 对于给定的输入，保证和为target 的不同组合数少于 150 个。
 * @Version 中等
 */
public class _39组合总和 {
    static int[] candidate = {2, 3, 6, 7};
    static int target = 7;
    @Test
    public void test(){
        List<List<Integer>> res = combinationSum(candidate, target);
        System.out.println(res);
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates, target, 0, 0);
        return res;
    }
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public void dfs(int[] candidates, int target, int sum, int index){
        if(index == candidates.length){
            return;
        }

        if(sum == target){
            res.add(new ArrayList<>(list));
            return;
        }

        //选
        if(sum + candidates[index] <= target){
            list.add(candidates[index]);
            dfs(candidates, target, sum + candidates[index], index);
            list.remove(list.size() - 1);
        }
        //不选
        dfs(candidates, target, sum, index + 1);
    }
}
